package com.gupao.datastructure.list;

/**
 * @description description
 * @author zhouxinghuai
 * @date 2018-09-20
 */
public class MyList {

    /**
     * 头结点插入
     * @param head
     * @param newhead
     */
    public static void headInsert(ListNode head, ListNode newhead) {
        newhead.next = head;
    }

    /**
     * 尾节点插入
     * @param tail
     * @param newtail
     */
    public static void tailInsert(ListNode tail, ListNode newtail) {
        tail.next = newtail;
        newtail.next = null;
    }

    /**
     * 遍历
     * @param head
     */
    public static void traverse(ListNode head) {
        while (head != null) {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
    }


    /**
     * 查找
     * @param head
     * @param value
     * @return
     */
    public static int find(ListNode head, int value) {
        int index = -1;
        int count = 0;
        while (head != null) {
            if (head.value == value) {
                index = count;
                return index;
            }
            count++;
            head = head.next;
        }
        return index;
    }

    /**
     * 插入
     * @param p
     * @param s
     */
    public static void insert(ListNode p, ListNode s) {
        ListNode next = p.next;
        p.next = s;
        s.next = next;
    }


    /**
     * 删除
     * @param head
     * @param q
     */
    public static void delete(ListNode head, ListNode q) {
        if (q != null && q.next != null) {
            ListNode next = q.next;
            q.value = next.value;
            // 删掉next.next
            q.next = next.next;
            next = null;
        }
        // 如果要删除的元素是最后一个元素，那么需要从头开始遍历，找到q的prev节点
        if (q.next == null) {
            while (head != null) {
                if (head.next == q) {
                    head.next = null;
                    break;
                }
                head = head.next;
            }
        }

    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        node1.next = node2;
        node2.next = node3;
        node3.next = null;

        traverse(node1);

        ListNode newhead = new ListNode(0);
        headInsert(node1, newhead);
        traverse(newhead);

        ListNode newtail = new ListNode(4);
        tailInsert(node3, newtail);
        traverse(newhead);

        System.out.println(find(newhead, 3));

        ListNode node = new ListNode(5);
        insert(node3, node);
        traverse(newhead);

    }
    
}
